package leetcode.dp;

public class LCS {
    public static void main(String[] args) {
        char[] arr1 = {'A','B','C','D','A','B'};
        char[] arr2 = {'B','D','C','A','B','C'};
        System.out.println(process(arr1,arr2,0,0));
        System.out.println(process(arr1,arr2));
    }
    public static int process(char[] arr1,char[] arr2,int i,int j){
        if (i>= arr1.length || j>=arr2.length){
            return 0;
        }
        if (arr1[i] == arr2[j]){
            return 1+process(arr1,arr2,i+1,j+1);
        }else {
            return Math.max(process(arr1,arr2,i,j+1),process(arr1,arr2,i+1,j));
        }
    }

    public static int process(char[] arr1,char[] arr2){
        int n = arr1.length;
        int m = arr2.length;
        int[][] ans = new int[n+1][m+1];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr1[i] == arr2[j]){
                    ans[i+1][j+1] = ans[i][j]+1;
                }else {
                    ans[i+1][j+1] = Math.max(ans[i+1][j],ans[i][j+1]);
                }
            }
        }
        return ans[n][m];
    }
}
